package vip.zhenzicheng.algorithm.leetcode.linked_list;

import vip.zhenzicheng.algorithm.ListNode;

/**
 * <a href="https://leetcode.cn/problems/reverse-nodes-in-k-group/">25. K个一组反转链表</a>
 *
 * @author zhenzicheng
 * @date: 2022-05-20 15:27
 */
public class ReverseNodesInKGroup_25 {

  public ListNode reverseKGroup(ListNode head, int k) {
    ListNode start = head;
    ListNode end = getKGroupEnd(start, k);

    if (end == null) {
      return head; // 不够直接返回
    }
    head = end; // 一定能交换成功，后面新的head就是末尾这个元素
    reverse(start, end);
    // 上一组的尾节点
    ListNode lastEnd = start;

    while (lastEnd.next != null) {
      start = lastEnd.next;
      end = getKGroupEnd(start, k);
      if (end == null) {
        return head;
      }
      reverse(start, end);

      lastEnd.next = end; // 修正上一次的尾节点指向新一组的头结点
      lastEnd = start;
    }

    return head;
  }

  // 从cur往下k个找到当前尾节点指针
  public ListNode getKGroupEnd(ListNode start, int k) {
    // 从cur往下k个找到当前尾节点指针
    while (--k > 0 && start != null) {
      start = start.next;
    }
    return start;
  }

  // 从start一直逆序到end
  public void reverse(ListNode start, ListNode end) {
    end = end.next; // 尾下移，表示下一组节点的头
    ListNode cur = start;
    ListNode pre = null;
    ListNode next = null;
    while (cur != end) { // 保证每一个节点都能遍历
      next = cur.next;
      cur.next = pre;
      pre = cur;
      cur = next;
    }
    // 此时start对应节点没有指向下一个子节点的头
    start.next = end;
  }

}
